package sword_to_1;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class LeeCode_35 {
    static class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }
    public static void main(String[] args) {
        Node l1 = new Node(7);
        Node l2 = new Node(13);
        Node l3 = new Node(11);
        Node l4 = new Node(10);
        Node l5 = new Node(1);
        l1.next = l2;
        l2.next = l3;
        l3.next = l4;
        l4.next = l5;
        l1.random = null;
        l2.random = l1;
        l3.random = l4;
        l4.random = l1;
        l5.random = l3;
        System.out.println(copyRandomList(l1));
    }
    private static Node copyRandomList(Node head) {
        if (head == null)
            return null;
        List<Node> list = new ArrayList<>();
        while (head != null){
            list.add(head);
            head = head.next;
        }
        int len = list.size();
        List<Node> list2 = new ArrayList<>(len);
        Map<Node, Integer> map = new HashMap<>();
        int i = 0;
        for (Node node : list) {
            list2.add(new Node(node.val));
            map.put(node, i++);
        }
        for (int j = 0; j < list.size(); j++) {
            if (list.get(j).random == null){
                list2.get(j).random = null;
            }else {
                int index = map.get(list.get(j).random);
                list2.get(j).random = list2.get(index);
            }
            if (j < len - 1)
                list2.get(j).next = list2.get(j + 1);
        }
        return list2.get(0);
    }
}
